package NC;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NC48 {
    public int search(int[] A, int target) {
        int position = 0;
        for (int i = 1; i < A.length; i ++) {
            if(A[i] < A[i - 1]) position = i - 1;
        }
        int search1 = binarySearch(A, 0, position, target);
        int search2 = binarySearch(A, position + 1, A.length - 1, target);
        if(search1 == - 1 && search2 == - 1) return - 1;
        return search1 == - 1 ? search2 : search1;
//        return binarySearch(A, 0, A.length-1, target);
    }
    public int binarySearch(int[] arr, int low, int high, int target) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if(arr[mid] < target) low = mid + 1;
            else if(arr[mid] > target) high = mid - 1;
            else return mid;
        }
        return - 1;
    }
}
